package com.atcumt.lcSolution;

import java.util.*;

// 字符串
public class LC1 {

    public static void main(String[] args) {

        LC1 solution = new LC1();

        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        solution.findRepeatedDnaSequences(s);
    }

    /**
     * 返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)
     * <p>
     * 思路：
     * 用 map 存储子串出现的次数，循环dna序列，每次截取长度为10的子串，
     * 加入 map 中并更新出现的次数，次数超过2，加入ans
     */
    public List<String> findRepeatedDnaSequences(String s) {

        Map<String, Integer> map = new HashMap<>();
        List<String> ans = new ArrayList<>();

        int n = s.length();
        for (int i = 0; i <= n - 10; i++) {
            String s1 = s.substring(i, i + 10);
            map.put(s1, map.getOrDefault(s1, 0) + 1);
            if (map.get(s1) == 2) {
                ans.add(s1);
            }
        }
        return ans;
    }

    /**
     * 字母异位词分组
     * <p>
     * 遍历字符串数组，对每个字符串中的字符排序，加入map对应的key的数组中
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(s);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 最长公共前缀
     * <p>
     * 纵向扫描字符串，找到第一个不相同的位置
     * 先循环字符串数组，再循环字符，找到第一个公共前缀不同的位置
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String ans = strs[0]; // ans初始值为字符串数组的第一个
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break; // 循环字符，找到第一个不相同的位置
                }
            }
            ans = ans.substring(0, j); // 从 0号位置到第一个不相同的位置截取字符串
            if (ans == "") {
                return ans;
            }
        }
        return ans;
    }
}
